1. Field of Invention
This invention is in the field of multiple resource allocation/routing to a plurality of resource destinations or tasks.
2. Description of the Related Art
Modern weapons are used in a battlefield where a plurality of targets can be engaged or tracked by multiple resources, e.g. weapons and sensors. In such a scenario, a routing problem arises: which resource to assign to a particular resource destination (task) such as target interception, tracking, and/or surveillance, and in what order. Resources are typically spatially distributed, may change position with time. Resource destinations may be stationary or moving. In view of the distributed, time changing nature of resources and resource destinations, and as their numbers increase, the allocation problem becomes complex. When allocating multiple resources (weapons, sensors, personnel) to engage multiple resource destinations (e.g. targets) it is desired to optimize allocation as a function many variables, such as time, distance from target(s), munitions capability, and/or target priority.
This allocation procedure is similar to the well known vehicle routing problem where many customers are to be visited, each at various locations separated by distances, typically in an irregular geometric pattern. Vehicle routing (resource allocation) among many customers (resource destination) may be optimized, for example, by minimizing the cost of each visit, i.e. total miles traveled. Another optimizing approach could be to visit those customers having higher priority first, or the closest ones, or the one's most likely to place a large order. From this simple illustration, it is apparent that the complexity of the solution to resource allocation increases as the number of resources (vehicles) and resource destinations (customers) increases.
Yet another dimension of complexity is added if each of a plurality of resources can be routed to any of a large number of resource destinations in real time. To illustrate the complexity of the problem, consider the scenario of an airline having hundreds of airplanes (resources) and dozens of airports to service (resource destinations). It is desired to optimize allocation of airplanes to travel certain routes, servicing the airports, subject to the constraints of passenger loading, profit maximization, fuel cost/maximum aircraft range and efficiency, perhaps weather avoidance. The plane allocation has to be computed in real time as weather patterns change, planes may be out of service, unavailable pilots/crew re-allocated. The solution to such a complex problem is computationally intensive, possibly precluded from arriving at an analytical result. Consequently, analytical results may become available too late to be practical.
The prior art approached a solution to this type of allocation problem by brute force. That is, each possible route and resource to resource destination routing possibility is computed to arrive at an absolutely optimal routing. The route best meeting the desired optimizing criterion is chosen after considering all route combinations. This approach presents an arduous computing task, impractical for a timely solution in a fast changing scenario where multiple resources (vehicles) can be allocated to many routes and respective resource destinations.